Skip to main content

22.02.28 - Higher-Order Functions

A function is Higher-Order if it takes a function as an argument or returns a function as a result

Why are they useful​

  • Common programming idioms can be encoded as functions within the language itself
  • Domain Specific Languages can be defined as collections of higher-order functions
  • Algebraic Properties of higher-order functions can be used to reason about programs

twice - calls a function twice map - applies a function to every item in a list filter - Selects every element from a list that satisfies a predicate

Foldr Function​

Number of functions on lists can be defined using the following simple pattern of recursion (primitive recursion):

f [] = v
f (x:xs) = x ? f xs

F maps the empty list to some value v, and any non-empty list to some function ? applied to its head and f of its tail.

foldr (fold right) - encapsulates this simple pattern of recursion with the function ? and the value v as arguments. Takes care of all the recursion. 

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v [] = v
foldr f v (x:xs) = f x (foldr f v xs)

f is the function, v is return statement, and [] is the list

Think foldr non-recursively, as simultaneously replacing each (:) in a list by a given function, and [] by a given value

Can be used to define many more functions than might first be expected

Foldr - Is building a function that does the matching and the recursion

Why its Useful​

  • Some recursive functions on list, such as sum, are simpler to define using foldr.
  • Properties of functions defined using foldr can be proved using algebraic properties of foldr, such as fusion and the banana split rule
  • Advanced program optimisations can be simplest if foldr is used in place of explicit recursion

Other Library Functions​

. returns the composition of two functions as a single function Function composition simple way of cascading or one function after another all decides if every element of a list satisfies a given predicate any decides if at least one element of a list satisfies a predicate takeWhile selects elements from a list while a predicate holds of all the elements dropWhile removes elements while a predicate holds of all the elements